Dynamic Programming 策略簡介

Dynamic Programming(動態規劃) 是一種解決問題的策略。

Dynamic Programming(動態規劃) 通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。

Dynamic Programming(動態規劃) 適用於有重疊子問題和最佳子結構性質的問題，Dynamic Programming(動態規劃)方法所耗時間往往比窮舉法少。

具體作法

Dynamic Programming(動態規劃) 第一步就是要找出原本問題的遞迴子問題結構。

先透過解決子問題來逐步解決大問題。

然後就可以透過把重複的子問題做快取來優化，因為避免了重複計算子問題結果。

一般來說會有兩種方式

Tabulation: bottom up

從子問題的結果開始計算往上累算。

Memorization: top down

從原問題往下遞迴推算。

雖然都是把已計算過的子問題結果透過快取紀錄下來

但計算順序方向不太相同。

Tabulation 的方式能夠減少遞迴所消耗的 call stack 。

以下是費式數列的範例

參考文獻

https://web.ntnu.edu.tw/~algo/DynamicProgramming.html

小故事

動態規劃把大問題拆解成小問題 然後把小問題解決來解決問題

好像感覺很熟析

古人有云：大事化小 小事化無

具體實踐，某公司開會時，同事 A 對現行工作分配制度提出了不滿。

於是主管就開始把他提出的問題拆解

於是開始問其他同事工作分配制度狀況

發現雖然大部份工作量都是交給同事 A 處理，但同事 B, C, D, E 並無不滿

原問題： 下屬對現行工作分配制度不滿 -> 子問題： 同事A 對現行工作分配制度不滿

因為只有同事 A 對工作分配制度不滿 所以只要解決這個子問題就沒問題了

所以把同事 A 解僱 -> 不存在有同事對工作分配制度不滿 -> 問題解決了！

筆者不是管理專家 但這聽起來很不錯吧（誤